#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;


//面试题 01.02.判定是否互为字符重排
//如果两个字符串互为重拍，那么说明这两个字符串的字符个数和类型全部相同
//借助hash表来分别标记两字符串。如果最后hash表中都为0，则说明两者互为重排


bool CheckPermutation(char* s1, char* s2)
{
    int hash[128] = { 0 };
    int len1 = strlen(s1);
    int len2 = strlen(s2);

    int i = 0;
    for (i = 0; i < len1; i++)
    {
        hash[s1[i]]++;
    }

    for (i = 0; i < len2; i++)
    {
        hash[s2[i]]--;
    }

    for (i = 0; i < 128; i++)
    {
        if (hash[i] != 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    char s1[] = "abc";
    char s2[] = "bca";
    if (CheckPermutation(s1, s2))
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }
    return 0;
}



//面试题 01.04.回文排列

bool ischaractersingle(char* s)
{
    size_t len = strlen(s);
    int i = 0;
    int left = 0;
    int right = len - 1;
    while (left <= right)
    {
        if (s[left++] != s[right--])
        {
            return false;
        }
    }
    return true;
}


bool canPermutePalindrome(char* s)
{
    //进行标记
    int hash[128] = { 0 };
    size_t len = strlen(s);

    int i = 0;
    for (i = 0; i < len; i++)
    {
        hash[s[i]]++;
    }

    //特殊情况：只有一种字符
    if (ischaractersingle(s))
    {
        goto ret;
    }
    else//普通情况
    {
        int flag = 0;
        if (len % 2 == 1)
        {
            //奇数
            //只有一个字符出现一次
            for (i = 0; i < 128; i++)
            {
                if (hash[i] % 2 != 0)
                {
                    flag++;
                }
                if (flag > 1)
                {
                    return false;
                }
            }
            goto ret;
        }
        else
        {
            //偶数
            //都出现了偶数次
            for (i = 0; i < 128; i++)
            {
                if (hash[i] % 2 != 0)
                {
                    return false;
                }
            }
        }
        goto ret;
    }
ret:
    return true;
}
